package com.le.tester.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * createTime：2024/4/17 13:28
 * description：括号生成
 */
public class Parenthesis {
    public List<String> generateParenthesis(int n) {

        StringBuilder sb = new StringBuilder();
        List<String> result = new ArrayList<>();
        dfs(n, sb, result, 0, 0);
        return result;

    }

    private void dfs(int n, StringBuilder sb, List<String> result, int i, int j) {

        //一次成功
        if (i == n && j == n) {
            result.add(sb.toString());
        }
        //这里可以把左边的括号全部考虑
        if (i < n) {
            sb.append("(");
            dfs(n, sb, result, i + 1, j);
            sb.deleteCharAt(sb.length() - 1);
        }

        //考虑右括号
        if (j < i) {
            sb.append(")");
            dfs(n, sb, result, i, j + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

}
